package com.atwulidun.dijkstra08;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class Dijkstra {
    public static void main(String[] args) {
        char[] data = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
        //邻接矩阵
        final int N = 65535;// 表示不可以连接
        int[][] weight = {
                {N, 5, 7, N, N, N, 2},
                {5, N, N, 9, N, N, 3},
                {7, N, N, N, 8, N, N},
                {N, 9, N, N, N, 4, N},
                {N, N, 8, N, N, 5, 4},
                {N, N, N, 4, 5, N, 6},
                {2, 3, N, N, 4, 6, N}};
        Graph graph = new Graph(data, weight, 2);
    }
}

class Graph {
    // 储存顶点信息的一维数组
    private char[] data;
    // 邻接矩阵
    private int[][] weight;

    // 记录顶点是否被访问过的一维数组
    private int[] isVisited;
    // 记录出发点到所有顶点最短距离的一维数组
    private int[] distance;
    // 记录所有顶点的前驱顶点的一维数组
    private int[] preVertex;

    // 构造方法，index指的是出发顶点的坐标
    public Graph(char[] data, int[][] weight, int index) {
        // 给data和weight初始化
        this.data = new char[data.length];
        this.weight = new int[data.length][data.length];
        for (int i = 0; i < data.length; i++) {
            this.data[i] = data[i];
            for (int j = 0; j < data.length; j++) {
                this.weight[i][j] = weight[i][j];
            }
        }

        // 给isVisited、distance和preVertex进行初始化
        isVisited = new int[data.length];
        distance = new int[data.length];
        preVertex = new int[data.length];
        // 把出发顶点设置为已经被访问
        isVisited[index] = 1;
        // 把出发顶点的距离设置为0，其他都设置为65535
        Arrays.fill(distance, 65535);
        distance[index] = 0;
        // 把所有顶点的前驱顶点都设置为-1
        Arrays.fill(preVertex, -1);

        // 接下来调用dijkstra方法
        dijkstra(index);;
        // 接下来打印出发顶点到各个顶点的最短路径
        System.out.println("出发顶点到各个顶点的最短路径如下：");
        printPath(index);
        // 接下来打印出发顶点到各个顶点的最短距离
        System.out.println("出发顶点到各个顶点的最短距离如下：");
        printDistance(index);
    }

    // 下面是与isVisited、distance和preVertex对应的方法
    // 返回一个顶点是否被访问过
    private boolean isVisited(int index) {
        return isVisited[index] == 1;
    }

    // 获取出发顶点到其中一个顶点的最短距离
    private int getDistance(int index) {
        return distance[index];
    }

    // 修改出发顶点到其中一个顶点的最短距离
    private void updateDistance(int index, int distance) {
        this.distance[index] = distance;
    }

    // 根据最后的distance打印出出发顶点到每个顶点的最短距离
    // index为出发顶点坐标
    private void printDistance(int index) {
        for (int i = 0; i < data.length; i++) {
            if (i != index) {
                System.out.println("顶点" + data[index] + "到顶点" + data[i] + "的最短距离为：" + distance[i]);
            }
        }
    }

    // 修改其中一个顶点的前驱顶点
    private void updatePreVertex(int index, int pre) {
        preVertex[index] = pre;
    }

    // 根据最后的preVertex打印出最后出发顶点到每个顶点的最短路径
    // index为出发顶点坐标
    private void printPath(int index) {
        // 定义一个栈来储存前驱结点，该栈可以循环利用，但是在使用之前一定要先清空
        Deque<Character> stack = new LinkedList<>();
        // 因为每一个顶点的最短路径都要打印出来，故用一个for循环
        for (int i = 0; i < data.length; i++) {
            // 把栈清空
            stack.clear();
            // 出发顶点就不需要打印出来了
            if (i != index) {
                // 这里是通过当前顶点不断地找前驱顶点，直到找到出发顶点
                int j = i;
                while (j != index) {
                    stack.push(data[j]);
                    // 找前驱顶点
                    j = preVertex[j];
                }
                System.out.print("顶点" + data[j] + "到顶点" + data[i] + "的最短路径为：" + data[j]);
                while (!stack.isEmpty()) {
                    System.out.print("->" + stack.pop());
                }
                System.out.println();
            }
        }
    }

    // 下面是与dijkstra对应的方法
    // 三部曲：1.update2.scan3.add
    // 根据index更新distance和preVertex
    private void update(int index) {
        int len = 0;
        // 找到邻接矩阵对应的index行，对其进行遍历
        for (int i = 0; i < weight[index].length; i++) {
            // 出发顶点到index的距离加上index到i的距离
            len = distance[index] + weight[index][i];
            if (isVisited[i] == 0 && len < distance[i]) {
                // 更新出发顶点到i的最短距离
                updateDistance(i, len);
                // 更新i的前驱顶点为index
                updatePreVertex(i, index);
            }
        }
    }

    // 在上面的update方法调用后，选择index的后继顶点，并返回其坐标
    // 其后继顶点应该为未被访问过，并且出发顶点到其距离最短
    private int scan() {
        int index = 0;
        int minDistance = 65535;
        // 对isVisited进行遍历
        for (int i = 0; i < isVisited.length; i++) {
            if (isVisited[i] == 0 && distance[i] < minDistance) {
                // 将出发顶点到当前顶点的距离赋值给minDistance
                minDistance = distance[i];
                // 将当前顶点的坐标记录下来
                index = i;
            }
        }
        // 将选择好的后继顶点标记为已经被访问
        // 对应三部曲的add
        isVisited[index] = 1;
        // 返回后继顶点的坐标
        return index;
    }

    // 先对顶点更新distance和preVertex，再选出一个后继顶点，对后继顶点更新distance和preVertex，再选出后继顶点再更新，直到所有的顶点都被选出更新为止
    // index为出发顶点的坐标
    private void dijkstra(int index) {
        // 更新出发顶点
        update(index);
        // 除了出发顶点外，还有data.length-1个顶点，故for循环从i=1开始
        for (int i = 1; i < data.length; i++) {
            // 找到一个后继顶点
            int sucVertex = scan();
            // 对该后继顶点进行更新
            update(sucVertex);
        }
    }
}
